package jm.data.structure.union_find;

/**
 * @Description QuickUnion size 优化版本
 * @date 2022/5/9 20:48
 */
public class QuickUnionSize extends AbstractUnionFind{

    // 记录当前元素的数量
    private int[] sizes;

    public QuickUnionSize(int capacity) {
        super(capacity);
        sizes = new int[capacity];
        // 将当前元素的数量默认为 1
        for (int i = 0; i < sizes.length; i++) {
            sizes[i] = 1;
        }
    }

    @Override
    public int find(int v) {
        rangeCheck(v);
        // 一直往上找 知道当前元素的父节点是自己就表示为根节点
        while (v != parents[v]){
            v = parents[v];
        }
        return v;
    }

    @Override
    public void union(int v1, int v2) {
        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 == p2) return;
        // 将数量少的嫁接到数量多的上面
        if (sizes[p1] < sizes[p2]){
            parents[p1] = p2;
            sizes[p2] += sizes[p1];
        }else {
            parents[p2] = p1;
            sizes[p1] += sizes[p2];
        }
    }
}
